SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Proximity problems</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Proximity problems</span></span>

</h1>

</header>

</p>

</p><p><b>Proximity problems</b> is a class of problems in <a href="Computational_geometry" title="Computational geometry">computational geometry</a> which involve estimation of <a href="Distance" title="Distance">distances</a> between geometric objects.

</p><p>A subset of these problems stated in terms of points only are sometimes referred to as <b>closest point problems</b>,<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> although the term "closest point problem" is also used synonymously to the <a href="Nearest_neighbor_search" title="Nearest neighbor search">nearest neighbor search</a>.

</p><p>A common trait for many of these problems is the possibility to establish the <a href="Big_O_notation" title="Big O notation">Θ</a>(<i>n</i> log <i>n</i>) <a href="Lower_bound" class="mw-redirect" title="Lower bound">lower bound</a> on their <a href="Computational_complexity_theory" title="Computational complexity theory">computational complexity</a> by reduction from the <a href="Element_uniqueness_problem" class="mw-redirect" title="Element uniqueness problem">element uniqueness problem</a> basing on an observation that if there is an efficient algorithm to compute some kind of minimal distance for a set of objects, it is trivial to check whether this distance equals to 0.

</p>

<div class="mw-heading mw-heading2"><h2 id="Atomic_problems">Atomic problems</h2></div>

<p>While these problems pose no computational complexity challenge, some of them are notable because of their ubiquity in computer applications of geometry.

</p>

<ul><li>Distance between a pair of <a href="Line_segment" title="Line segment">line segments</a>. It cannot be expressed by a single formula, unlike, e.g., the <a href="Distance_from_a_point_to_a_line" title="Distance from a point to a line">distance from a point to a line</a>. Its calculation requires careful enumeration of possible configurations, especially in 3D and higher dimensions.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup></li>

<li><a href="Bounding_box" class="mw-redirect" title="Bounding box">Bounding box</a>, the minimal axis-aligned <a href="Hyperrectangle" title="Hyperrectangle">hyperrectangle</a> that contains all geometric data</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Problems_on_points">Problems on points</h2></div>

<ul><li><a href="Closest_pair_of_points" class="mw-redirect" title="Closest pair of points">Closest pair of points</a>: Given N points, find two with the smallest distance between them</li>

<li><a href="Closest_point_query" class="mw-redirect" title="Closest point query">Closest point query</a> / <a href="Nearest_neighbor_query" class="mw-redirect" title="Nearest neighbor query">nearest neighbor query</a>: Given N points, find one with the smallest distance to a given query point</li>

<li>All nearest neighbors problem (construction of the <a href="Nearest-neighbor_graph" class="mw-redirect" title="Nearest-neighbor graph">nearest-neighbor graph</a>): Given N points, find a closest one for each of them</li>

<li><a href="Diameter_(computational_geometry)" title="Diameter (computational geometry)">Diameter (computational geometry)</a>: Given N points, find two with the largest distance between them</li>

<li>Width of a point set: Given N points, find two (hyper)planes with the smallest distance between them and with all points between them</li>

<li><a href="Minimum_spanning_tree" title="Minimum spanning tree">Minimum spanning tree</a> for a set of points

<ul><li><a href="Euclidean_minimum_spanning_tree" title="Euclidean minimum spanning tree">Euclidean minimum spanning tree</a></li></ul></li>

<li><a href="Delaunay_triangulation" title="Delaunay triangulation">Delaunay triangulation</a></li>

<li><a href="Voronoi_diagram" title="Voronoi diagram">Voronoi diagram</a></li>

<li><a href="Smallest_enclosing_sphere" class="mw-redirect" title="Smallest enclosing sphere">Smallest enclosing sphere</a>: Given N points, find a smallest sphere (circle) enclosing them all</li>

<li><a href="Largest_empty_circle" class="mw-redirect" title="Largest empty circle">Largest empty circle</a>: Given N points in the plane, find a largest circle centered within their <a href="Convex_hull" title="Convex hull">convex hull</a> and enclosing none of them</li>

<li><a href="Smallest_enclosing_rectangle" class="mw-redirect" title="Smallest enclosing rectangle">Smallest enclosing rectangle</a>: unlike the <a href="Bounding_box" class="mw-redirect" title="Bounding box">bounding box</a> problem mentioned above, the rectangle may be of any orientation</li>

<li><a href="Largest_empty_rectangle" title="Largest empty rectangle">Largest empty rectangle</a></li>

<li><a href="Geometric_spanner" title="Geometric spanner">Geometric spanner</a>, a <a href="Weighted_graph" class="mw-redirect" title="Weighted graph">weighted graph</a> over a set of points as its vertices which for every pair of vertices has a path between them of weight at most 'k' times the spatial distance between these points for a fixed 'k'.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Other">Other</h2></div>

<ul><li>Shortest path among obstacles</li>

<li><a href="Distance_of_closest_approach_of_ellipses_and_ellipsoids" class="mw-redirect" title="Distance of closest approach of ellipses and ellipsoids">Distance of closest approach</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFFranco_P._Preparata_and_Michael_Ian_Shamos1985" class="citation book cs1"><a href="Franco_P._Preparata" title="Franco P. Preparata">Franco P. Preparata</a> and <a href="Michael_Ian_Shamos" title="Michael Ian Shamos">Michael Ian Shamos</a> (1985). <span class="id-lock-registration" title="Free registration required"><a rel="nofollow" class="external text" href="https://archive.org/details/computationalgeo0000prep"><i>Computational Geometry - An Introduction</i></a></span>. <a href="Springer-Verlag" class="mw-redirect" title="Springer-Verlag">Springer-Verlag</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-387-96131-3</bdi>. 1st edition: <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-387-96131-3</bdi>; 2nd printing, corrected and expanded, 1988: <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>3-540-96131-3</bdi>; Russian translation, 1989: <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>5-03-001041-6</bdi>.</cite> The proximity problems are covered in chapters 6 and 7.</li></ul>

<li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text"><cite id="CITEREFJ._R._Sack_and_J._Urrutia_(eds.)2000" class="citation book cs1"><a href="J._R._Sack" class="mw-redirect" title="J. R. Sack">J. R. Sack</a> and <a href="Jorge_Urrutia_(professor)" class="mw-redirect" title="Jorge Urrutia (professor)">J. Urrutia</a> (eds.) (2000). <i>Handbook of Computational Geometry</i>. <a href="North_Holland" title="North Holland">North Holland</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-444-82537-1</bdi>.</cite> <span class="cs1-visible-error citation-comment"><code class="cs1-code">{{cite book}}</code>: </span><span class="cs1-visible-error citation-comment"><code class="cs1-code">|author=</code> has generic name (help)</span></span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><cite id="CITEREFV._J._Lumelsky1985" class="citation journal cs1">V. J. Lumelsky (1985). "On fast computation of distance between line segments". <i><a href="Information_Processing_Letters" title="Information Processing Letters">Inf. Process. Lett.</a></i> <b>21</b> (2): <span class="nowrap">55–</span>61. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0020-0190%2885%2990032-8">10.1016/0020-0190(85)90032-8</a>.</cite></span>

</li>

</ol></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-12-27" href="https://en.wikipedia.org/wiki/?title=Proximity_problems&oldid=1265450234">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>